package com.universe.arithmetic.baseSort;

import com.universe.util.ArrayUtil;

/**
 * @Author：ghostbamboo
 * @Description： 基数排序
 * @Theory： 基数排序问题：
 * 1)基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或 bin sort，
 * 顾 名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用。
 * 2) 基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法。
 * 3) 基数排序(Radix Sort)是桶排序的扩展。
 * 4) 基数排序是 1887 年赫尔曼·何乐礼发明的。它是这样实现的：将整数按位数切割成不同的数字，然后按每个位数分别比较。
 * 简而言之：将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。
 * 这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
 * 平均时间复杂度 O（n * k） 空间复杂度 O（n * k）
 * @Date： 09:21 2019/12/21
 */
public class RadixSort {


    public static void radixSort(int... arr) {
        //定义桶
        int[][] bucket = new int[10][arr.length];
        //定义各个桶元素的数量
        int[] counts = new int[10];
        //最大元素的长度, 以确认需要执行几轮
        int maxLength = 0;
        //最大值,为得出maxLength
        int maxValue = 0;

        //----------------------- 1 -----------------------------
        //获取最大值位数, 便于确认需要执行到几分位的桶,(最大值1000就是千分位)
        for (int value : arr) {
            if (maxValue < value) {
                maxValue = value;
            }
        }
        maxLength = (maxValue + "").length();

        //----------------------- 2 -----------------------------
        //取出元素放入桶中
        for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
            for (int j = 0; j < arr.length; j++) {
                //获取该元素对应位的值
                int positionOfElement = arr[j] / n % 10;
                //放入对应位的桶中
                bucket[positionOfElement][counts[positionOfElement]] = arr[j];
                //对应桶元素数量加1
                counts[positionOfElement]++;
            }

            //----------------------- 3 -----------------------------
            //取出桶中的元素放回数组
            int index = 0;
            for (int j = 0; j < counts.length; j++) {
                if (counts[j] != 0) {
                    for (int k = 0; k < counts[j]; k++) {
                        arr[index++] = bucket[j][k];
                    }
                    //置空该位元素的数量
                    counts[j] = 0;
                }
            }
        }

    }


    public static void main(String[] args) {
        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        int[] copy = ArrayUtil.copyArray(arr);

        radixSort(arr);
        ArrayUtil.systemSort(copy);
        boolean success = ArrayUtil.isEqual(arr, copy);
        System.out.println(success ? "Nice! 排序成功" : "What a pity! Failed!!!");
        for (int i : arr) {
            System.out.print(i + " ");
        }

    }
}
